package com.mtons.datastructure.tree.binarytree;

public class BinaryTree implements Tree {

    private BinaryNode root;

    // 查找节点
    public BinaryNode find(int key){
        BinaryNode current = root;
        while (current != null) {
            //当前值比查找值大，搜索左子树
            if (current.data > key) {
                current = current.leftChild;
                //当前值比查找值小，搜索右子树
            }else if (current.data < key) {
                current = current.rightChild;
            } else {
                return current;
            }
        }
        return null;
    }

    /**
     * 插入节点
     * @param data
     * @return
     */
    public boolean insert(int data) {
        BinaryNode newBinaryNode = new BinaryNode(data);

        //当前树为空树，没有任何节点
        if (root == null) {
            root = newBinaryNode;
            return true;
        } else {
            BinaryNode current = root;
            BinaryNode parent = null;
            while (current != null) {
                parent = current;
                if (current.data > data) {
                    current = current.leftChild;
                    if (current == null) {
                        parent.leftChild = newBinaryNode;
                        return true;
                    }
                } else {
                    current = current.rightChild;
                    if (current == null) {
                        parent.rightChild = newBinaryNode;
                        return true;
                    }
                }
            }
        }
        return false;
    }

    // 中序遍历
    public void infixOrder(BinaryNode current) {
        if (current != null) {
            infixOrder(current.leftChild);
            System.out.println(current.data);
            infixOrder(current.rightChild);
        }
    }

    // 前序遍历
    public void preOrder(BinaryNode current) {
        if (current != null) {
            System.out.println(current.data);
            preOrder(current.leftChild);
            preOrder(current.rightChild);
        }
    }

    // 后序遍历
    public void postOrder(BinaryNode current) {
        if (current != null) {
            postOrder(current.leftChild);
            postOrder(current.rightChild);
            System.out.println(current.data);
        }
    }

    // 查找最大值
    public BinaryNode findMax() {
        BinaryNode current = root;
        BinaryNode maxBinaryNode = current;
        while (current != null) {
            maxBinaryNode = current;
            current = current.rightChild;
        }
        return maxBinaryNode;
    }

    // 查找最小值
    public BinaryNode findMin() {
        BinaryNode current = root;
        BinaryNode minBinaryNode = current;
        while (current != null) {
            minBinaryNode = current;
            current = current.leftChild;
        }
        return minBinaryNode;
    }

    // 删除节点
    public boolean delete(int key) {
        BinaryNode current = root;
        BinaryNode parent = root;
        boolean isLeftChild = false;

        //查找删除值，找不到直接返回false
        while (current.data != key) {
            parent = current;
            if (current.data > key) {
                isLeftChild = true;
                current = current.leftChild;
            } else {
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null) {
                return false;
            }
        }

        //如果当前节点没有子节点
        if (current.leftChild == null && current.rightChild == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.leftChild = null;
            } else {
                parent.rightChild = null;
            }
            return true;
            //当前节点有一个子节点，右子节点
        } else if (current.leftChild == null && current.rightChild != null) {
            if (current == root) {
                root = current;
            } else if (isLeftChild) {
                parent.leftChild = current.rightChild;
            } else {
                parent.rightChild = current.rightChild;
            }
            return true;
            //当前节点有一个子节点，左子节点
        } else if (current.leftChild != null && current.rightChild == null) {
            if (current == root) {
                root = current;
            } else if (isLeftChild) {
                parent.leftChild = current.leftChild;
            } else {
                parent.rightChild = current.leftChild;
            }
            return true;
            //当前节点存在两个子节点
        } else {
            BinaryNode successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.leftChild = successor;
            } else {
                parent.rightChild = successor;
            }
            successor.leftChild = current.leftChild;
        }

        return false;
    }

    public BinaryNode getSuccessor(BinaryNode delBinaryNode) {
        BinaryNode successorParent = delBinaryNode;
        BinaryNode successor = delBinaryNode;
        BinaryNode current = delBinaryNode.rightChild;
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }
        //后继节点不是删除节点的右子节点，将后继节点替换删除节点
        if (successor != delBinaryNode.rightChild) {
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delBinaryNode.rightChild;
        }
        return successor;
    }
}


